<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>Example 7.4: Binary hypothesis testing</title>
<link rel="canonical" href="/Users/mcgrant/Repos/CVX/examples/cvxbook/Ch07_statistical_estim/html/detector2.html">
<link rel="stylesheet" href="../../../examples.css" type="text/css">
</head>
<body>
<div id="header">
<h1>Example 7.4: Binary hypothesis testing</h1>
Jump to:&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#source">Source code</a>&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#output">Text output</a>
&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#plots">Plots</a>
&nbsp;&nbsp;&nbsp;&nbsp;<a href="../../../index.html">Library index</a>
</div>
<div id="content">
<a id="source"></a>
<pre class="codeinput">
<span class="comment">% Figure 7.4</span>
<span class="comment">% Boyd &amp; Vandenberghe "Convex Optimization"</span>
<span class="comment">% Original version by Lieven Vandenberghe</span>
<span class="comment">% Updated for CVX by Michael Grant, 2005-12-19</span>

<span class="comment">% Generate the data</span>
P = [0.70  0.10
     0.20  0.10
     0.05  0.70
     0.05  0.10];
[n,m] = size(P);

<span class="comment">% Construct the tradeoff curve by finding the</span>
<span class="comment">% the Pareto optimal deterministic detectors,</span>
<span class="comment">% which are the curve's vertices</span>

nopts   = 1000;
weights = logspace(-5,5,nopts);
obj     = [0;1];
inds    = ones(n,1);

<span class="comment">% minimize  -t1'*q1 - w*t2'*q2</span>
<span class="comment">% s.t.      t1+t2 = 1,  t1,t2 \geq 0</span>

next = 2;
<span class="keyword">for</span> i = 1 : nopts,
   PW = P * diag( [ 1 ; weights(i) ] );
   [ maxvals, maxinds ] = max( PW' );  <span class="comment">% max elt in each row</span>
   <span class="keyword">if</span> (~isequal(maxinds', inds(:,next-1)))
       inds(:,next) = maxinds';
       T = zeros(m,n);
       <span class="keyword">for</span> j=1:n
          T(maxinds(1,j),j) = 1;
       <span class="keyword">end</span>;
       obj(:,next) = 1-diag(T*P);
       next = next+1;
   <span class="keyword">end</span>;
<span class="keyword">end</span>;
plot(obj(1,:), obj(2,:),[0 1], [0 1],<span class="string">'--'</span>);
grid <span class="string">on</span>
<span class="keyword">for</span> i=2:size(obj,2)-1
   text(obj(1,i),obj(2,i),[<span class="string">'a'</span>, num2str(i-1)]);
<span class="keyword">end</span>;

<span class="comment">% Minimax detector: not deterministic</span>

cvx_begin
    variables <span class="string">T( m, n )</span> <span class="string">D( m, m )</span>
    minimize <span class="string">max( D(1,2), D(2,1) )</span>
    subject <span class="string">to</span>
        D == T * P;
        sum( T, 1 ) == 1;
        T &gt;= 0;
cvx_end

objmp = 1 - diag( D );
text( objmp(1), objmp(2), <span class="string">'b'</span> );
xlabel(<span class="string">'P_{fp}'</span>); ylabel(<span class="string">'P_{fn}'</span>);

<span class="comment">%print -deps roc.eps</span>
</pre>
<a id="output"></a>
<pre class="codeoutput">
 
Calling Mosek 9.1.9: 10 variables, 5 equality constraints
------------------------------------------------------------

MOSEK Version 9.1.9 (Build date: 2019-11-21 11:32:15)
Copyright (c) MOSEK ApS, Denmark. WWW: mosek.com
Platform: MACOSX/64-X86

Problem
  Name                   :                 
  Objective sense        : min             
  Type                   : LO (linear optimization problem)
  Constraints            : 5               
  Cones                  : 0               
  Scalar variables       : 10              
  Matrix variables       : 0               
  Integer variables      : 0               

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 4
Eliminator terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries                  : 2                 time                   : 0.00            
Lin. dep.  - tries                  : 1                 time                   : 0.00            
Lin. dep.  - number                 : 0               
Presolve terminated. Time: 0.00    
Problem
  Name                   :                 
  Objective sense        : min             
  Type                   : LO (linear optimization problem)
  Constraints            : 5               
  Cones                  : 0               
  Scalar variables       : 10              
  Matrix variables       : 0               
  Integer variables      : 0               

Optimizer  - threads                : 8               
Optimizer  - solved problem         : the primal      
Optimizer  - Constraints            : 1
Optimizer  - Cones                  : 0
Optimizer  - Scalar variables       : 6                 conic                  : 0               
Optimizer  - Semi-definite variables: 0                 scalarized             : 0               
Factor     - setup time             : 0.00              dense det. time        : 0.00            
Factor     - ML order time          : 0.00              GP order time          : 0.00            
Factor     - nonzeros before factor : 1                 after factor           : 1               
Factor     - dense dim.             : 0                 flops                  : 1.30e+01        
ITE PFEAS    DFEAS    GFEAS    PRSTATUS   POBJ              DOBJ              MU       TIME  
0   2.0e+00  2.0e+00  6.0e+00  0.00e+00   2.000000000e+00   0.000000000e+00   4.0e+00  0.00  
1   4.1e-01  4.1e-01  1.2e+00  2.33e+00   5.271701753e-01   4.421583667e-01   8.1e-01  0.01  
2   4.8e-02  4.8e-02  1.4e-01  1.01e+00   2.187626321e-01   2.057396942e-01   9.6e-02  0.01  
3   5.4e-03  5.4e-03  1.6e-02  9.95e-01   1.722986032e-01   1.704628420e-01   1.1e-02  0.01  
4   6.9e-05  6.9e-05  2.1e-04  1.00e+00   1.666975808e-01   1.666681082e-01   1.4e-04  0.01  
5   7.0e-09  7.0e-09  2.1e-08  1.00e+00   1.666666698e-01   1.666666668e-01   1.4e-08  0.01  
Basis identification started.
Primal basis identification phase started.
Primal basis identification phase terminated. Time: 0.00
Dual basis identification phase started.
Dual basis identification phase terminated. Time: 0.00
Basis identification terminated. Time: 0.00
Optimizer terminated. Time: 0.01    


Interior-point solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: 1.6666666981e-01    nrm: 1e+00    Viol.  con: 2e-09    var: 2e-09  
  Dual.    obj: 1.6666666684e-01    nrm: 7e-01    Viol.  con: 0e+00    var: 2e-09  

Basic solution summary
  Problem status  : PRIMAL_AND_DUAL_FEASIBLE
  Solution status : OPTIMAL
  Primal.  obj: 1.6666666667e-01    nrm: 1e+00    Viol.  con: 0e+00    var: 3e-17  
  Dual.    obj: 1.6666666251e-01    nrm: 7e-01    Viol.  con: 0e+00    var: 7e-18  
Optimizer summary
  Optimizer                 -                        time: 0.01    
    Interior-point          - iterations : 5         time: 0.01    
      Basis identification  -                        time: 0.00    
        Primal              - iterations : 0         time: 0.00    
        Dual                - iterations : 0         time: 0.00    
        Clean primal        - iterations : 0         time: 0.00    
        Clean dual          - iterations : 0         time: 0.00    
    Simplex                 -                        time: 0.00    
      Primal simplex        - iterations : 0         time: 0.00    
      Dual simplex          - iterations : 0         time: 0.00    
    Mixed integer           - relaxations: 0         time: 0.00    

------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): +0.166667
 
</pre>
<a id="plots"></a>
<div id="plotoutput">
<img src="detector2__01.png" alt=""> 
</div>
</div>
</body>
</html>